{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 为什么要使用PER\n",
    "\n",
    "在强化学习场景中**采样**是一个非常重要的步骤，常用的采样方法是DQN中的随机采样，然而在实际训练过程中某些样本更为重要或更难以训练，随机采样会“忽视”对这部分难分样本的训练，从而导致训练出的智能体表现较差。《深度强化学习》给出了一个例子，无人车大部分时间都在正常行驶，很少会出现碰撞的情况，这就导致随机采样会较少地采样到“碰撞”样本，进而导致智能体不能合理地处置碰撞情况；考虑到“碰撞”样本训练地较少，训练时可以增加对这类样本的采样频率。\n",
    "\n",
    "Rainbow的实验结果指出，PER是最影响智能体表现的技巧之一，缺少PER会导致智能体的表现变得很差。\n",
    "\n",
    "#### PER的算法原理及过程\n",
    "1. PER对于样本是否优先的评价指标是**TD-error**，即$\\delta=|R+max \\gamma Q'(s',a;\\theta)-Q(s,a)|$。\n",
    "2. 在一个包含k个样本的批次中，PER的采样概率从原来的P(i)=1/N变为：\n",
    "   $$P(i)=\\frac{p_{i}}{\\sum_{i=1}^k p_{k}}$$\n",
    "   $p_{i}$的计算方法有两种：$p_{i}=|\\delta_{i}+\\epsilon|$或$p_{i}=\\frac{1}{rank(i)}$\n",
    "3. 改变难分样本的采样概率会导致模型收敛方向发生变化（因为采样的分布发生了变化），因此根据重要性采样，需要在损失函数中乘以一个重要性权重。\n",
    "   $$\\omega _{i}=(\\frac{1}{N} \\cdot \\frac{1}{P(i)})^ \\beta$$\n",
    "   超参数$\\beta$表示训练时有多大程度想抵消PER对模型收敛结果的影响，$\\beta$为0表示不进行抵消，为1表示完全抵消（即和DQN的随机采样没有区别）。\n",
    "   在实验中需要对重要性权重进行归一化来保证收敛的稳定性，即：\n",
    "   $$\\omega _{i}=(N \\cdot P(i))^{-\\beta}/max_{i}\\omega_{i}$$\n",
    "4. 综合起来，损失函数变为：\n",
    "   $$y_{j}=r+\\gamma \\cdot {Q_{target}(s_{j},\\mathop{max}\\limits_{a}{Q_{evaluate}(s_{j},a)};\\theta^{-}) }$$\n",
    "   $$Loss=\\frac{1}{m} \\sum_{j=1}^{m} \\omega_{j}(y_{j}-Q_{evaluate}(s_{j-1},a_{j-1};\\theta))^2$$\n",
    "   于是梯度为：\n",
    "   $$\\Delta\\leftarrow\\Delta+\\omega_{j}\\cdot \\delta_{j}\\cdot \\nabla_{\\theta}Q(S_{j-1},A_{j-1})$$\n",
    "\n",
    "#### PER为什么要使用SumTree代替线性经验回放\n",
    "1. 原始的线性经验回放应用在PER中的过程是：保存每一笔经验的$p_{i}=|\\delta_{i}+\\epsilon|$，然后在[0,total]区间上均匀采样，再根据得到的结果进行O(n)时间复杂度的筛选。\n",
    "2. 现代深度强化学习经验回放的大小在十万到百万之间，且这个数量对训练结果影响很大，一般不能减小经验回放的大小。如果使用线性表存放TD-error，会在采样阶段消耗大量时间（一次采样消耗O(n)时间），因此PER提出了树形结构来减小时间开销。\n",
    "3. 定义一个根据数字s来采样节点的算法：从根节点开始比较，即idx=0，如果左边的子节点比s大，则走左边子节点这条，如果左边子节点小于s，则走右子节点，但s值要减去左子节点的数值，按照这个规则，一直找到叶结点，返回其索引、对应的p值，以及对应的transition。\n",
    "<img style=\"display:block;margin:0 auto\" src=\"PER伪代码.png\" width=958.1 height=568.1>\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "DL_test",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
